package com.huawei.M01.iterator.A23;

import java.util.Arrays;
import java.util.Map;

/**
 * 书架
 *
 * @author zhiwu
 */
public class Shelves {
    public int minHeightShelves(int[][] books, int shelfWidth) {
        int len = books.length;
        int[] dp = new int[len + 1];
        Arrays.fill(dp, 1000000);
        dp[0] = 0;
        for (int i = 0; i < len; i++) {
            int curWidth = 0;
            int maxHeight = 0;
            for (int j = i; j >= 0; j--) {
                curWidth += books[j][0];
                if (curWidth > shelfWidth) {
                    break;
                }
                maxHeight = Math.max(maxHeight, books[j][1]);
                dp[i + 1] = Math.min(dp[i + 1], dp[j] + maxHeight);
            }
        }

        return dp[len];
    }

    public static void main(String[] args) {
        System.out.println(new Shelves().minHeightShelves(new int[][]{
                {7, 3},
                {8, 7},
                {2, 7},
                {2, 5}
        }, 10));
    }

//    [1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]
}
